

cdef float ORIENT_2D(float a[2],float b[2],float c[2]):
    return (a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0])


cdef int INTERSECTION_TEST_VERTEX(float P1[2],float Q1[2],float R1[2],float P2[2],float Q2[2],float R2[2]) : 
    if ORIENT_2D(R2,P2,Q1) >= 0.0:
        if ORIENT_2D(R2,Q2,Q1) <= 0.:
            if (ORIENT_2D(P1,P2,Q1) > 0.) :
                if (ORIENT_2D(P1,Q2,Q1) <= 0.) :
                    return 1 
                else:
                    return 0
            else :
                if (ORIENT_2D(P1,P2,R1) >= 0.):
                    if (ORIENT_2D(Q1,R1,P2) >= 0.):
                        return 1 
                    else :
                        return 0
                else :
                    return 0
        else :
            if (ORIENT_2D(P1,Q2,Q1) <= 0.):
                if (ORIENT_2D(R2,Q2,R1) <= 0.):
                    if (ORIENT_2D(Q1,R1,Q2) >= 0.):
                        return 1 
                    else :
                        return 0
                else :
                    return 0
            else :
                return 0
    else :
        if (ORIENT_2D(R2,P2,R1) >= 0.) :
            if (ORIENT_2D(Q1,R1,R2) >= 0.) :
                if (ORIENT_2D(P1,P2,R1) >= 0.):
                    return 1
                else :
                    return 0
            else :
                if (ORIENT_2D(Q1,R1,Q2) >= 0.) :
                    if (ORIENT_2D(R2,R1,Q2) >= 0.):
                        return 1 
                    else:
                        return 0
                else:
                    return 0 
        else :
            return 0 



cdef int INTERSECTION_TEST_EDGE(float P1[2],float Q1[2],float R1[2],float P2[2],float Q2[2],float R2[2]) :
    if (ORIENT_2D(R2,P2,Q1) >= 0.) :
        if (ORIENT_2D(P1,P2,Q1) >= 0.)  :
            if (ORIENT_2D(P1,Q1,R2) >= 0.):
                return 1 
            else :
                return 0
        else :
            if (ORIENT_2D(Q1,R1,P2) >= 0.) :
                if (ORIENT_2D(R1,P1,P2) >= 0.):
                    return 1
                else :
                    return 0
            else :
                return 0
    else :
        if (ORIENT_2D(R2,P2,R1) >= 0.) :
            if (ORIENT_2D(P1,P2,R1) >= 0.) :
                if (ORIENT_2D(P1,R1,R2) >= 0.):
                    return 1  
                else :
                    if (ORIENT_2D(Q1,R1,R2) >= 0.):
                        return 1
                    else:
                        return 0
            else:
                return 0
        else :
            return 0


#def ccw_tri_tri_intersection_2d(float p1[2], float q1[2], float r1[2], 

cdef int ccw_tri_tri_intersection_2d(float p1[2],float q1[2], float r1[2],float p2[2],float q2[2],float r2[2]) :
    if ( ORIENT_2D(p2,q2,p1) >= 0. ):
        if ( ORIENT_2D(q2,r2,p1) >= 0. ) :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ):
                return 1
            else :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,p2,q2,r2)
        else :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ) :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,r2,p2,q2)
            else :
                return INTERSECTION_TEST_VERTEX(p1,q1,r1,p2,q2,r2)
    else :
        if ( ORIENT_2D(q2,r2,p1) >= 0. ) :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ) :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,q2,r2,p2)
            else :
                return INTERSECTION_TEST_VERTEX(p1,q1,r1,q2,r2,p2)
        else :
            return INTERSECTION_TEST_VERTEX(p1,q1,r1,r2,p2,q2)


cdef  int tri_tri_overlap_test_2d(float p1[2],float  q1[2], float r1[2],float p2[2],float  q2[2], float r2[2]) :
    if ( ORIENT_2D(p1,q1,r1) < 0. ):
        if ( ORIENT_2D(p2,q2,r2) < 0. ):
            return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,r2,q2)
        else:
            return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,q2,r2)
    else:
        if ( ORIENT_2D(p2,q2,r2) < 0. ) :
            return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,r2,q2)
        else :
            return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,q2,r2)

def triangleOverlapTest(A, B):
    # takes two numpy float arrays [3,2] as input, returns a int 1 or 0 if intersection 
    cdef int i
    cdef float P[6][2]
    
    for i in range(3):
        P[i][0]=A[i][0]
        P[i][1]=A[i][1]
        P[i+3][0]=B[i][0]
        P[i+3][1]=B[i][1]
        
    return tri_tri_overlap_test_2d(P[0],P[1],P[2],P[0],P[1],P[2])
    
